10126. Pairs

 

Array of unique integers and a target value k are given. Determine the number of pairs of array elements that have a difference equal to a target value k.

 

Input. First line contains integers n (2 ≤ n ≤ 105) and k (0 < k < 109). Second line contains n unique integers in the range from 0 to 231 – 1.

 

Output. Print the number of pairs of array integers with difference k.

 

Sample input

Sample output

6 3

7 3 5 1 10 2

2

 

 

SOLUTION

set

 

Algorithm analysis

Insert all numbers into the set s. Then iterate over the elements of the set and for each its value x check whether the set contains the number x + k. Count the number of such pairs x and x + k, for which both numbers belong to the set.

 

Example

Consider the set in the result of sorting:

At the distance k = 3 there are two pairs of elements: (2, 5) è (7, 10).

 

Algorithm realization

Read the input data. Read the input array into the set s.

 

scanf("%d %d", &n, &k);

for (i = 0; i < n; i++)

{

  scanf("%d", &x);

  s.insert(x);

}

 

The number of required pairs is computed in the variable res.

 

res = 0;

 

Iterate over the elements of the set. For each value x from s, check whether s contains the number x + k. If so, then increase the value of res.

 

for (int x : s)

  if (s.find(x + k) != s.end()) res++;

 

Print the answer.

 

printf("%d\n", res);

 

Java realization

 

import java.util.*;

 

public class Main

{

  public static void main(String []args)

  {

    Scanner con = new Scanner(System.in);

    TreeSet<Integer> s = new TreeSet<Integer>();

    int n = con.nextInt();

    int k = con.nextInt();

    for(int i = 0; i < n; i++)

    {

      int x = con.nextInt();

      s.add(x);

    }

 

    int res = 0;

    for(int x : s)

      if (s.contains(x + k)) res++;

 

    System.out.println(res);

    con.close();

  }

}